home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Camelot / Camelot 043 (1989-06)(Swedish User Group of Amiga)(SE)(PD)[WB].zip / Camelot 043 (1989-06)(Swedish User Group of Amiga)(SE)(PD)[WB].adf / zc / nodes.c < prev    next >
C/C++ Source or Header  |  1989-03-08  |  9KB  |  558 lines
  1. /* Copyright (c) 1988 by Sozobon, Limited.  Author: Johann Ruegg
  2.  *
  3.  * Permission is granted to anyone to use this software for any purpose
  4.  * on any computer system, and to redistribute it freely, with the
  5.  * following restrictions:
  6.  * 1) No charge may be made other than reasonable charges for reproduction.
  7.  * 2) Modified versions must be clearly marked as such.
  8.  * 3) The authors are not responsible for any harmful consequences
  9.  *    of using this software, even if they result from defects in it.
  10.  *
  11.  *    nodes.c
  12.  *
  13.  *    Node allocation, deallocation, searching, printing
  14.  *    and other node handling
  15.  */
  16.  
  17. #include <stdio.h>
  18. #include "param.h"
  19. #include "nodes.h"
  20.  
  21. extern FILE *output;
  22. NODE *freelist;
  23.  
  24. #define NODEINCR    100
  25.  
  26. extern int oflags[];
  27. #define debug oflags['n'-'a']
  28.  
  29. #define NODELEN    (sizeof(NODE)/4)
  30.  
  31. int nodesmade, nodesavail;
  32.  
  33. NODE *
  34. allocnode()
  35. {
  36.     char *calloc();
  37.     NODE *t;
  38.     int i;
  39.  
  40. retry:
  41.     if (freelist != 0) {
  42.         t = freelist;
  43.         freelist = t->n_next;
  44.         lclr(t, NODELEN);
  45.         nodesavail--;
  46.         if (debug)
  47.             printf("%lx+ ", t);
  48.         return t;
  49.     }
  50.     t = (NODE *)calloc(NODEINCR, sizeof(NODE));
  51.     if (t == 0) {
  52.         printf("malloc failure\n");
  53.         exit(1);
  54.     }
  55.     nodesmade += NODEINCR;
  56.     nodesavail += NODEINCR;
  57.     for (i=0; i<NODEINCR; i++)
  58.         t[i].n_next = &t[i+1];
  59.     t[NODEINCR-1].n_next = 0;
  60.     freelist = t;
  61.     goto retry;
  62. }
  63.  
  64. freeunit(t)
  65. NODE *t;
  66. {
  67.     if (t->n_flags & N_ISFREE) {
  68.         printf("%lx ", t);
  69.         error("Freeing free node");
  70.         exit(1);
  71.     } else
  72.         t->n_flags |= N_ISFREE;
  73.     t->n_next = freelist;
  74.     freelist = t;
  75.     nodesavail++;
  76.     if (debug)
  77.         printf("%lx- ", t);
  78. }
  79.  
  80. freenode(t)
  81. NODE *t;
  82. {
  83.     register NODE *nxt;
  84.  
  85.     if (t == NULL) return;
  86. again:
  87.     if (t->n_right)
  88.         freenode(t->n_right);
  89.     if (t->n_nmx)
  90.         freenode(t->n_nmx);
  91.     if (t->n_tptr && (t->n_flags & N_COPYT) == 0)
  92.         freenode(t->n_tptr);
  93.     nxt = t->n_left;
  94.     freeunit(t);
  95.     if (nxt) {
  96.         t = nxt;
  97.         goto again;    /* minimize left recursion */
  98.     }
  99. }
  100.  
  101. put_nnm(t)
  102. NODE *t;
  103. {
  104.     printf("%s", t->n_name);
  105.     while (t->n_nmx) {
  106.         t = t->n_nmx;
  107.         printf("%s", t->n_name);
  108.     }
  109. }
  110.  
  111. qput_nnm(t, fd)
  112. NODE *t;
  113. FILE *fd;
  114. {
  115.     fprintf(fd, "%s", t->n_name);
  116.     while (t->n_nmx) {
  117.         t = t->n_nmx;
  118.         fprintf(fd, "%s", t->n_name);
  119.     }
  120. }
  121.  
  122. fput_nnm(t)
  123. NODE *t;
  124. {
  125.     fprintf(output, "%s", t->n_name);
  126.     while (t->n_nmx) {
  127.         t = t->n_nmx;
  128.         fprintf(output, "%s", t->n_name);
  129.     }
  130. }
  131.  
  132. /* add a short string (less than NMXSIZE) to front of name */
  133. nnmins(t, s)
  134. NODEP t;
  135. char *s;
  136. {
  137.     register i, j;
  138.     char tbuf[NMSIZE];
  139.     NODEP n;
  140.  
  141.     i = strlen(t->n_name);
  142.     j = strlen(s);
  143.     if (j > NMSIZE-1)
  144.         return;        /* compiler error */
  145.     if (i+j <= NMSIZE-1) {        /* fits in node */
  146.         strcpy(tbuf, t->n_name);
  147.         strcpy(t->n_name, s);
  148.         strcpy(t->n_name+j, tbuf);
  149.     } else {
  150.         n = allocnode();
  151.         n->n_nmx = t->n_nmx;
  152.         t->n_nmx = n;
  153.         strcpy(n->n_name, t->n_name);
  154.         strcpy(t->n_name, s);
  155.     }
  156. }
  157.  
  158. /* add a short string (less than NMXSIZE) to end of name */
  159. nnmadd(t, s)
  160. NODE *t;
  161. char *s;
  162. {
  163.     register i,j;
  164.     int sizeb;
  165.     NODEP n;
  166.  
  167.     /* find last node */
  168.     sizeb = NMSIZE;
  169.     while (t->n_nmx) {
  170.         t = t->n_nmx;
  171.         sizeb = NMXSIZE;
  172.     }
  173.     /* fits in current last node? */
  174.     i = strlen(s);
  175.     j = strlen(t->n_name);
  176.     if (i < sizeb-j) {
  177.         strcat(t->n_name, s);
  178.         return;
  179.     }
  180.     /* put all of s in new node */
  181.     n = allocnode();
  182.     t->n_nmx = n;
  183.     t = n;
  184.     strncpy(t->n_name, s, NMXSIZE-1);
  185.     t->n_name[NMXSIZE-1] = 0;
  186. }
  187.  
  188. nscpy(t, s)
  189. NODE *t;
  190. char *s;
  191. {
  192.     register i;
  193.     NODEP n;
  194.  
  195.     i = strlen(s);
  196.     strncpy(t->n_name, s, NMSIZE-1);
  197.     t->n_name[NMSIZE-1] = 0;
  198.     i -= NMSIZE-1;
  199.     s += NMSIZE-1;
  200.     while (i > 0) {
  201.         n = allocnode();
  202.         t->n_nmx = n;
  203.         t = n;
  204.         strncpy(t->n_name, s, NMXSIZE-1);
  205.         t->n_name[NMXSIZE-1] = 0;
  206.         i -= NMXSIZE-1;
  207.         s += NMXSIZE-1;
  208.     }
  209. }
  210.  
  211. putlist(head, np)
  212. NODE **head, *np;
  213. {
  214.     np->n_next = *head;
  215.     *head = np;
  216. }
  217.  
  218. puthlist(head, np)
  219. NODE *head[], *np;
  220. {
  221.     putlist(&head[hash(np->n_name)], np);
  222. }
  223.  
  224. NODE *
  225. llook(head, np)
  226. NODE *head, *np;
  227. {
  228.     register NODEP p;
  229.  
  230.     for (p=head; p != NULL; p = p->n_next)
  231.         if (xstrcmp(p, np) == 0) {
  232.             return p;
  233.         }
  234.     return NULL;
  235. }
  236.  
  237. NODE *
  238. hlook(head, np)
  239. NODE *head[], *np;
  240. {
  241.     register NODEP p;
  242.  
  243.     p = head[hash(np->n_name)];
  244.     return llook(p, np);
  245. }
  246.  
  247. hash(s)
  248. register char *s;
  249. {
  250.     register hval;
  251.  
  252.     hval = 0;
  253.     while (*s)
  254.         hval += *s++;
  255.     return hval & (NHASH-1);
  256. }
  257.  
  258. xstrcmp(p1, p2)
  259. NODE *p1, *p2;
  260. {
  261.     int rv;
  262.  
  263.     if ((rv = strcmp(p1->n_name, p2->n_name)) != 0)
  264.         return rv;
  265.     if (p1->n_nmx == NULL) {
  266.         if (p2->n_nmx == NULL)
  267.             return 0;
  268.         return -1;
  269.     }
  270.     if (p2->n_nmx == NULL)
  271.         return 1;
  272.     return xstrcmp(p1->n_nmx, p2->n_nmx);
  273. }
  274.  
  275. char *
  276. scopy(s)
  277. char *s;
  278. {
  279.     int i;
  280.     char *p;
  281.  
  282.     i = strlen(s)+1;
  283.     if (i > sizeof(NODE)) {
  284.         error("preproc name too big");
  285.         i = sizeof(NODE);
  286.         s[i-1] = 0;
  287.     }
  288.     p = (char *)allocnode();
  289.     strcpy(p, s);
  290.     return p;
  291. }
  292.  
  293. sfree(s)
  294. char *s;
  295. {
  296.     NODEP np;
  297.  
  298.     np = (NODEP)s;
  299.     np->n_flags = 0;
  300.     freeunit(np);
  301. }
  302.  
  303. printlist(np)
  304. NODE *np;
  305. {
  306.     putchar('\n');
  307.     prln(np, 2);
  308. }
  309.  
  310. prln(np, indent)
  311. NODE *np;
  312. {
  313.     register NODE *svl, *nxtl;
  314.  
  315.     for (svl=np; svl != NULL; svl = nxtl) {
  316.         nxtl = svl->n_next;
  317.         svl->n_next = NULL;
  318.         prnode(svl,indent);
  319.         svl->n_next = nxtl;
  320.         /* special hack for tag list */
  321.         if ((svl->n_flags & N_BRKPR) && svl->n_right)
  322.             prln(svl->n_right, indent+2);
  323.     }
  324. }
  325.  
  326. codeprint(np)
  327. NODEP np;
  328. {
  329.     putchar('\n');
  330.     cprnode(np,0);
  331. }
  332.  
  333. cprnode(np,indent)
  334. NODE *np;
  335. {
  336.     int ni;
  337.     NODEP tp;
  338.  
  339.     ni = indent+1;
  340.     while (indent--)
  341.         putchar(' ');
  342.     if (np == NULL) {
  343.         printf("<NULL>\n");
  344.         return;
  345.     }
  346.     put_nnm(np);    /* Note: BRKPR doesnt break long names */
  347.     if (np->g_offs)
  348.         printf(" o%ld ", np->g_offs);
  349.     if (np->g_rno)
  350.         printf(" r%d ", np->g_rno);
  351.     if (np->g_needs)
  352.         printf(" n%x ", np->g_needs);
  353.     if (debug) {
  354.         printf("@%lx ", np);
  355.         if (np->n_flags & N_COPYT)
  356.             printf("C ");
  357.         if (np->n_flags & N_BRKPR)
  358.             printf("B ");
  359.     }
  360.     if (np->n_flags & N_BRKPR) {
  361.         putchar('\n');
  362.         return;
  363.     }
  364.     if (np->g_betw)
  365.         printf(" {%s}", np->g_betw);
  366.     if (np->g_code) {
  367.         if (np->n_flags & N_COPYT)
  368.             printf(" <%s>", np->g_code);
  369.         else
  370.             for (tp=np->g_code; tp; tp = tp->g_code)
  371.                 printf(" <%s>", tp->n_name);
  372.     }
  373.     putchar(' ');
  374.     out_a(np, stdout);
  375.     putchar('\n');
  376.     if (np->n_left) {
  377.         cprnode(np->n_left,ni);
  378.     } else if (np->n_right)
  379.         cprnode(NULL, ni);
  380.     if (np->n_right) {
  381.         cprnode(np->n_right,ni);
  382.     }
  383. }
  384.  
  385. printnode(np)
  386. NODE *np;
  387. {
  388.     putchar('\n');
  389.     prnode(np,0);
  390. }
  391.  
  392. prnode(np,indent)
  393. NODE *np;
  394. {
  395.     int ni;
  396.  
  397.     ni = indent+1;
  398.     while (indent--)
  399.         putchar(' ');
  400.     if (np == NULL) {
  401.         printf("<NULL>\n");
  402.         return;
  403.     }
  404.     put_nnm(np);    /* Note: BRKPR doesnt break long names */
  405.     if (np->e_offs)
  406.         printf(" o%ld ", np->e_offs);
  407.     if (np->e_rno)
  408.         printf(" r%d ", np->e_rno);
  409.     if (np->e_fldw)
  410.         printf(" (%d,%d) ", np->e_fldw, np->e_fldo);
  411.     if (debug) {
  412.         printf("@%lx ", np);
  413.         if (np->n_flags & N_COPYT)
  414.             printf("C ");
  415.         if (np->n_flags & N_BRKPR)
  416.             printf("B ");
  417.     }
  418.     if (np->n_flags & N_BRKPR) {
  419.         putchar('\n');
  420.         return;
  421.     }
  422.     if (np->n_tptr) {
  423.         if (np->e_flags & 256)    /* IMMEDID */
  424.             printf(" $$$ ");
  425.         tprint(np->n_tptr);
  426.     }
  427.     putchar('\n');
  428.     if (np->n_left) {
  429.         prnode(np->n_left,ni);
  430.     } else if (np->n_right)
  431.         prnode(NULL, ni);
  432.     if (np->n_right) {
  433.         prnode(np->n_right,ni);
  434.     }
  435. }
  436.  
  437. tprint(np)
  438. NODEP np;
  439. {
  440.     while (np != NULL) {
  441.         putchar(' ');
  442.         put_nnm(np);
  443. #ifdef HANS
  444.         if (np->t_size)
  445.             printf(" s%ld", np->t_size);
  446.         if (np->t_aln)
  447.             printf(" a%d", np->t_aln);
  448. #endif
  449.         if (debug)
  450.             printf("@%lx", np);
  451.         np = np->n_tptr;
  452.     }
  453. }
  454.  
  455. NODEP
  456. copynode(op)
  457. NODEP op;
  458. {
  459.     NODEP np;
  460.  
  461.     if (op == NULL) return NULL;
  462.     np = allocnode();
  463.     lcpy(np, op, NODELEN);
  464.     if (np->n_nmx)
  465.         np->n_nmx = copynode(np->n_nmx);
  466.     if (np->n_right)
  467.         np->n_right = copynode(np->n_right);
  468.     if (np->n_left)
  469.         np->n_left = copynode(np->n_left);
  470.     if (np->n_tptr)
  471.         np->n_flags |= N_COPYT;
  472.     return np;
  473. }
  474.  
  475. NODEP
  476. copyone(op)
  477. NODEP op;
  478. {
  479.     NODEP np;
  480.  
  481.     if (op == NULL) return NULL;
  482.     np = allocnode();
  483.     lcpy(np, op, NODELEN);
  484.     if (np->n_nmx)
  485.         np->n_nmx = copyone(np->n_nmx);
  486.     if (np->n_right)
  487.         np->n_right = NULL;
  488.     if (np->n_left)
  489.         np->n_left = NULL;
  490.     if (np->n_tptr)
  491.         np->n_flags |= N_COPYT;
  492.     return np;
  493. }
  494.  
  495. NODEP
  496. copy_nol(op)
  497. NODEP op;
  498. {
  499.     NODEP np;
  500.  
  501.     if (op == NULL) return NULL;
  502.     np = allocnode();
  503.     lcpy(np, op, NODELEN);
  504.     if (np->n_nmx)
  505.         np->n_nmx = copynode(np->n_nmx);
  506.     if (np->n_right) /* break right links */
  507.         np->n_right = NULL;
  508.     if (np->n_tptr)
  509.         np->n_flags |= N_COPYT;
  510.     return np;
  511. }
  512.  
  513. NODEP
  514. copylist(np, tailp)
  515. NODE *np, **tailp;
  516. {
  517.     NODEP rv, nx;
  518.     register NODEP tail;
  519.  
  520.     if (np == NULL) {
  521.         *tailp = NULL;
  522.         return NULL;
  523.     }
  524.     rv = copy_nol(np);
  525.     tail = rv;
  526.     while (tail->n_left) {
  527.         nx = copy_nol(tail->n_left);
  528.         tail->n_left = nx;
  529.         tail = nx;
  530.     }
  531.     *tailp = tail;
  532.     return rv;
  533. }
  534.  
  535. NODE *
  536. nthnode(np, n)
  537. NODE *np;
  538. {
  539.     while (n--)
  540.         if (np == NULL)
  541.             return NULL;
  542.         else
  543.             np=np->n_next;
  544.     return np;
  545. }
  546.  
  547. NODE *
  548. rthnode(np, n)
  549. NODE *np;
  550. {
  551.     while (n--)
  552.         if (np == NULL)
  553.             return NULL;
  554.         else
  555.             np=np->n_right;
  556.     return np;
  557. }
  558.